package pl.edu.mimuw.irs.core.util.bipartite;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

import pl.edu.mimuw.irs.core.util.graph.Edge;

public class ExponentialMaxMatch implements MaxMatch {

	// *** Attributes

	private Map<Object, Wrapper> sourceWrappers;
	private Map<Object, Wrapper> targetWrappers;
	private List<Edge> wrappedLinks;
	public Map<Object, Wrapper> getSourceWrappers() {
		if (sourceWrappers == null) sourceWrappers = new LinkedHashMap<Object, Wrapper>();
		return sourceWrappers;
	}
	public void setSourceWrappers(Map<Object, Wrapper> sourceWrappers) {
		this.sourceWrappers = sourceWrappers;
	}
	public Map<Object, Wrapper> getTargetWrappers() {
		if (targetWrappers == null) targetWrappers = new LinkedHashMap<Object, Wrapper>();
		return targetWrappers;
	}
	public void setTargetWrappers(Map<Object, Wrapper> targetWrappers) {
		this.targetWrappers = targetWrappers;
	}
	public List<Edge> getWrappedLinks() {
		return wrappedLinks;
	}
	public void setLinks(List<Edge> edges) {
		this.wrappedLinks = new ArrayList<Edge>();
		for (Edge link : edges) {
			Object object1 = link.getContainedNode(getSourceWrappers().keySet());
			Wrapper wrapper1 = getSourceWrappers().get(object1);
			Object object2 = link.getContainedNode(getTargetWrappers().keySet());
			Wrapper wrapper2 = getTargetWrappers().get(object2);
			wrappedLinks.add(new Edge(wrapper1, wrapper2));
		}
	}
	
	// *** Constructors
	
	public ExponentialMaxMatch(List<?> source, List<?> target, List<Edge> edges) {
		for (Wrapper wrapper : wrapElements(source)) {
			getSourceWrappers().put(wrapper.getContent(), wrapper);
		}
		for (Wrapper wrapper : wrapElements(target)) {
			getTargetWrappers().put(wrapper.getContent(), wrapper);
		}
		setLinks(edges);
	}
	
	// *** Methods
	
	public List<List<Edge>> findAllMaxMatches() {
		List<List<Edge>> maxMatchesSet = new LinkedList<List<Edge>>();
		
		findAllMaxMatches(0, new LinkedList<Edge>(), maxMatchesSet);
		
		return maxMatchesSet;
	}
	
	private void findAllMaxMatches(int position, List<Edge> maxMatch, List<List<Edge>> maxMatchesSet) {
		if (position == getWrappedLinks().size()) {
			if (maxMatchesSet.size() > 0 &&
					((List<Edge>)maxMatchesSet.get(0)).size() < maxMatch.size()) {
				maxMatchesSet.clear();
			}
			
			if (maxMatchesSet.size() == 0 ||
					(((List<Edge>)maxMatchesSet.get(0)).size() == maxMatch.size())) {
				List<Edge> copy = new ArrayList<Edge>(maxMatch);
				maxMatchesSet.add(copy);
			}

			return;
		}
		Edge link = getWrappedLinks().get(position);
		if (!((Wrapper)link.getNode1()).isUsed() &&
				!((Wrapper)link.getNode2()).isUsed()) {
			((Wrapper)link.getNode1()).setUsed(true);
			((Wrapper)link.getNode2()).setUsed(true);
			Edge tmpEdge = new Edge(((Wrapper)link.getNode1()).getContent(), ((Wrapper)link.getNode2()).getContent());
			maxMatch.add(tmpEdge);
			findAllMaxMatches(position + 1, maxMatch, maxMatchesSet);
			maxMatch.remove(tmpEdge);
			((Wrapper)link.getNode1()).setUsed(false);
			((Wrapper)link.getNode2()).setUsed(false);
		}
		findAllMaxMatches(position + 1, maxMatch, maxMatchesSet);
	}
	
	private Set<Wrapper> wrapElements(List<?> source) {
		Set<Wrapper> wrappedElements = new HashSet<Wrapper>();
		for (Object object : source) {
			wrappedElements.add(new Wrapper(object));
		}
		return wrappedElements;
	}

	// *** Inner classes
	
	private class Wrapper {
		
		// *** Attributes
		
		private Object content;
		private boolean used;
		public Object getContent() {
			return content;
		}
		public void setContent(Object content) {
			this.content = content;
		}
		public boolean isUsed() {
			return used;
		}
		public void setUsed(boolean used) {
			this.used = used;
		}
		
		// *** Constructors
		
		public Wrapper(Object content) {
			setContent(content);
			setUsed(false);
		}
		
		// *** Methods
		
		@Override
		public String toString() {
			return "Wrapper(" + getContent() + ")";
		}
		
	}
	
	enum TestSource {
		A,
		B, 
		C, 
	}
	enum TestTarget {
		A,
		AC,
		B, 
		BC,
	}
	
	public static void main(String[] args) {
		List<Object> source = new LinkedList<Object>();
		source.addAll(Arrays.asList(new Object[]{TestSource.A, TestSource.B, TestSource.C}));
		List<Object> target = new LinkedList<Object>();
		target.addAll(Arrays.asList(new Object[]{TestTarget.A, TestTarget.AC, TestTarget.B, TestTarget.BC}));
		List<Edge> edges = new LinkedList<Edge>();
		edges.add(new Edge(TestSource.A, TestTarget.A));
		edges.add(new Edge(TestSource.A, TestTarget.AC));
		edges.add(new Edge(TestSource.B, TestTarget.B));
		edges.add(new Edge(TestSource.B, TestTarget.BC));
		edges.add(new Edge(TestSource.C, TestTarget.BC));
		edges.add(new Edge(TestSource.C, TestTarget.AC));
		
		ExponentialMaxMatch maxMatch = new ExponentialMaxMatch(
				source, target, edges);
		
		List<List<Edge>> list = maxMatch.findAllMaxMatches();
		for (List<Edge> match : list) {
			System.out.println(match);
		}
	}

}
